# 7/100 双指针-接雨水
# leetcode第42题: https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/15

import json

from leetcode import test


def trap(height: list[int]) -> int:
    """模拟方法-超时
    """
    n = len(height)
    res = 0
    l, r = 0, 1
    while r < n and n - l > 2:
        if height[l] < height[r]:  # 保证l->r是一个下降的过程
            r += 1
            l += 1
        else:
            t = 0  # 用于存储水底突出的临时变量
            maxh, maxh_i = 0, 0  #
            while r < n and height[r] < height[l]:  # 向后查找可以和l组成一个坑的r, 如果l是最大值, 那么提前寻找次一级的水坑
                r += 1
                if r == n:
                    break
                maxh = max(maxh, height[r])
                if maxh == height[r]:
                    maxh_i = r
            if r == n:  # 表示没有比height[l] 更大的数了
                r = maxh_i
            # 计算这个坑的雨水量
            w = r - l - 1
            h = min(height[r], height[l])
            for i in range(l + 1, r):
                t += height[i] if height[i] < h else h
            res += (w * h - t)

            # 进行下一次循环
            l = r
            r += 1

    return res


def trap_dp(height: list[int]) -> int:
    """使用动态规划的方法
    对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，
    下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
    首先对整个数组进行正反两个方向的扫描, 并定义两个数组表示每个位置上其左(右)侧柱子的最大值
    这样对两个数组进行覆盖求其对应位置上的较小值就是这个坑的水位线的位置
    使用水位线的位置减去其自身的位置, 就是装水量
    """
    n = len(height)
    dpl, dpr = [0] * n, [0] * n
    maxv, res = 0, 0
    for i in range(n):
        maxv = max(maxv, height[i])
        dpl[i] = maxv
    maxv = 0
    for j in range(n - 1, -1, -1):
        maxv = max(maxv, height[j])
        dpr[j] = maxv
    for k in range(n):
        res += min(dpl[k], dpr[k]) - height[k]
    return res


def trap_dbpnt(height: list[int]) -> int:
    """使用双指针的方法, 双指针的方法是对动态规划方法的一种优化.
    在动态规划的做法中, 需要维护长度为n的两个数组, 那么如何减少空间复杂度?
    到下标i处的能接的雨水量由dpr[i]和dpl[i]中的较小值决定, 这两个数组就可以使用两个指针来代替
    """
    l, r = 0, len(height) - 1
    lmax, rmax = 0, 0
    res = 0
    while l < r:
        lmax = max(lmax, height[l])
        rmax = max(rmax, height[r])
        if rmax > lmax:
            res += lmax - height[l]
            l += 1
        else:
            res += rmax - height[r]
            r -= 1
    return res


def trap_dbpnt_opt(height: list[int]) -> int:
    """优化了lMax和rMax的更新的过程
    """
    l, r = 0, len(height) - 1
    lmax, rmax = height[l], height[r]
    res = 0
    while l < r:
        if rmax > lmax:
            res += lmax - height[l]
            l += 1
            if l <= r: lmax = max(lmax, height[l])
        else:
            res += rmax - height[r]
            r -= 1
            if l <= r: rmax = max(rmax, height[r])
    return res


def trap_stack(height: list[int]) -> int:
    """使用单调栈的方法
    单调栈可以解决的问题比较单一: 在数组中寻找下一个更大(小)的元素.
    首先让遍历的当前元素入栈, 如果当前元素大(小)于栈顶元素, 那么就让当前元素出栈, 否则则保持在栈内的状态, 直到有元素大于该元素再出栈
    下面就是一个通过单调栈来查找每个元素右侧更大元素的过程, 注意栈内的元素应存储为索引而不是数值, 这里仅为方便理解.
    arr     4   2   0   3   2   5       arr     4   2   0   3   2   5       arr     4   2   0   3   2   5
            i                                       i                                       i
    stack   4                           stack   4   2                       stack   4   2   0
    res     -1                          res     -1  -1                      res     -1  -1  -1

    arr     4   2   0   3   2   5       arr     4   2   0   3   2   5       arr     4   2   0   3   2   5
                        i                                       i                                       i
    stack   4                           stack   4                           stack
    res     -1  3   3                   res    -1   3   3   2               res     5   3   3   2   5

    对于本题来说, 需要查找每个位置中左右两侧都大于第i个元素的位置(即左右侧的柱子).
    对于单调栈来说, 显然右侧的柱子就是下一个更大的元素, 记当前元素就是栈顶top, 那么左侧的柱子即为栈内top的下一个元素即为left.
    """
    stack = []
    res = 0
    for i, v in enumerate(height):
        while stack and v > height[stack[-1]]:
            top = stack.pop()
            if not stack:  # 如果栈空则跳过
                break
            left = stack[-1]
            we = i - left - 1
            he = min(height[left], height[i]) - height[top]
            res += we * he
        stack.append(i)

    return res


if __name__ == '__main__':
    n1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    n2 = [4, 2, 0, 3, 2, 5]
    n3 = [3, 0, 2, 1, 2]
    n4 = [3, 1, 2, 1, 2, 3]
    n5 = [5, 4, 1, 2]
    with open("../data/b_dbpnt4_lc42.data", "r") as file:
        lines = file.read().strip()  # 去除首位的空白
        n6 = json.loads(lines)

    inp = [{"height": n1}, {"height": n2}, {"height": n3}, {"height": n4}, {"height": n5}, {"height": n6}]
    out = [6, 9, 3, 6, 1, 949905000]

    # test.test_function(trap, inp, out)
    test.test_function(trap_dp, inp, out)
    test.test_function(trap_dbpnt, inp, out)
    test.test_function(trap_dbpnt_opt, inp, out)
    test.test_function(trap_stack, inp, out)

